//
// Created by liushuai on 12/21/19.
//
#include "climbStairs2.h"
int climbStairs2(int n){
    std::vector<int> mem(n+1);
    return climbStairs2(0,n,mem);
}
int climbStairs2(int n, int m, std::vector<int> mem) {
    if (n > m)
        return 0;
    else if (n == m)
        return 1;
    else {
        if (mem.at(m) > 0)
            return mem[m];
        else {
            mem.at(m) = climbStairs2(n + 1, m, mem) + climbStairs2(n + 2, m, mem);
            return mem.at(m);
        }

    }
}